#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Node {
  public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

struct edge {
    int to;
    edge* next;
    edge() : to(-1), next(nullptr) {}
    edge(int to) : to(to), next(nullptr) {}
    edge(int to, edge* next) : to(to), next(next) {}
};

bool visited[103];
Node* created[103];
Node* cloneGraph(Node* node) {
    if(node == nullptr) return nullptr;
    int nodeNum=0;
    // make my graph
    edge vertex[103];
    edge* tail[103];
    for(int i=0;i<103;i++) tail[i] = &vertex[i];

    queue<Node*> Q;
    Q.push(node);
    nodeNum++;
    visited[node->val] = 1;
    while(!Q.empty()){
        Node* p = Q.front();
        for(int i=0;i<p->neighbors.size();i++){
            tail[p->val]->next = new edge(p->neighbors[i]->val);
            tail[p->val] = tail[p->val]->next;
            if(!visited[p->neighbors[i]->val]){
                visited[p->neighbors[i]->val] = 1;
                nodeNum++;
                Q.push(p->neighbors[i]);
            }
        }
        Q.pop();
    }


    // new graph
    Node* ans = new Node(1);
    queue<Node*> NQ;
    NQ.push(ans);
    created[1] = ans;
    while(!NQ.empty()){
        Node* p = NQ.front();
        edge* q = &vertex[p->val];
        while(q->next){
            q = q->next;
            if(created[q->to] == nullptr){
                Node* newNode = new Node(q->to);
                created[q->to] = newNode;
                p->neighbors.push_back(newNode);
                NQ.push(newNode);
            }else{
                p->neighbors.push_back(created[q->to]);
            }
        }
        NQ.pop();
    }

    return created[1];
}
